package nan.Mysort;

import java.util.Arrays;

public class MySort {
    public static void mergeSortByLoop(int[] arr){
        //gap用于限定分组，gap值的含义就是每个待归并数组的长度
        int gap=1;
        for(;gap< arr.length;gap=gap*2){
            //当前两个待归并的数组
            for(int i=0;i< arr.length;i=i+2*gap){
                //在这个循环中控制两个相邻数组进行归并
                //[left,mid)和[mid,right)进行归并
                int left=i;
                int mid=i+gap;
                if(mid>= arr.length){
                    mid=arr.length;
                }
                int right=i+2*gap;
                if(right>arr.length){
                    right= arr.length;
                }
                merge(arr,left,mid,right);
            }
        }
    }
    //归并排序
    public static void mergeSort(int[] arr){
        _mergeSort(arr,0,arr.length);
    }

    public static void _mergeSort(int[] arr,int left,int right){
        //辅助递归方法
        if(right-left<=1){//判定当前区间是不是只有一个元素或者没有元素
            //此时不需要进行排序
            return;
        }
        int mid=(left+right)/2;
        //先让[left,mid)变成有序
        //再让[mid,right)变成有序
        _mergeSort(arr,left,mid);
        _mergeSort(arr,mid,right);
        merge(arr,left,mid,right);
    }
    //归并排序中的关键操作，就是归并两个有序数组
    //使用该merge方法完成数组归并的过程
    //[left,mid)左侧数组
    // [mid,right)右侧数组
    public static void merge(int[] arr,int left,int mid,int right){
        //进行具体的归并，临时空间大小：right-left；
        if(left>=right){
            return;
        }
        int[] tmp=new int[right-left];
        int tmpIndex=0;//表示当前元素该放到临时空间的哪个位置
        int cur1=left;
        int cur2=mid;
        while (cur1<mid&&cur2<right){
            if(arr[cur1]<=arr[cur2]){
                //把cur1对应的元素插入到临时空间中，
                tmp[tmpIndex]=arr[cur1];
                tmpIndex++;
                cur1++;
            }else{
                //把cur2对应的元素插入到临时空间去
                tmp[tmpIndex]=arr[cur2];
                tmpIndex++;
                cur2++;
            }
        }
        //循环结束之后，需要把最后剩余的元素也都拷贝到最终结果里。
        while(cur1<mid){
            tmp[tmpIndex]=arr[cur1];
            tmpIndex++;
            cur1++;//左侧有剩余
        }
        while (cur2<right){
            tmp[tmpIndex]=arr[cur2];
            tmpIndex++;
            cur2++;//右侧有剩余
        }
        //还需要把tmp的结果放回arr数组
        for(int i=0;i<tmp.length;i++){
            arr[left+i]=tmp[i];
        }
    }

    //快速排序
    public static void quickSort(int[] arr){
        _quickSort(arr,0,arr.length-1);//辅助递归的方法，在这个方法的参数中，
        // 明确针对哪个区间进行递归
        //[0，length-1]
    }
    public static void _quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        //先针对当前[left,right]区间进行partition操作，
        // Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，
        // 将比基准值大的（可以包含相等的）放到基准值的右边
        //方法的返回值，表示整理完当前区间后，基准值所在的位置，
        // 即遍历过程中的left和right的重合位置
        int index=partition(arr,left,right);
        //递归的对左侧区间进行快速排序
        _quickSort(arr, left, index-1);
        //递归的对右侧区间进行快速排序
        _quickSort(arr,index+1,right);
    }
    public static int partition(int[] arr,int left,int right){
        //选取最右侧元素作为基准值
        int val=arr[right];
        int l=left;
        int r=right;
        //如果l和r重合，说明遍历完成
        while(l<r){
            //先从左往右，找一个比基准值大的数字
            while (l<r&&arr[l] <= val) {
                l++;
            }//当循环结束的时候，l就指向了比基准值大的元素
            //再从右往左找一个比基准值小的数字
            while (l<r&&arr[r]>=val){
                r--;
            }
            swap(arr,l,r);
        }
        //当l和r重合的时候，就把重合位置的元素和基准值位置进行交换
        swap(arr,l,right);
        //最终方法返回基准值所在的位置
        return l;
    }


    //冒泡排序
    public static void bubbleSort(int[] array){
        boolean flag=false;//定义一个布尔类型的变量flag，作为判断每趟结束
        // 之后是否已经是有序序列
        for(int i=0;i< array.length-1;i++){//定义趟数，
            // 趟数为array.length-1
            for(int j=0;j< array.length-1-i;j++){//定义每次下标之间的比
                // 较，每次数组下标之间的比较次数都要比上一次少一趟，
                // 要是array[j]>array[j+1]，就交换数据
                flag=false;//每一趟都要将flag置位false
                if(array[j]>array[j+1]){
                    int tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;//交换数据
                    flag=true;//如果发生交换，就把flag置位true；
                }
            }
            if(flag==false){//说明在这趟比较中没有进入if交换
                break;
            }
        }
    }
    //堆排序
    public static void heapSort(int[] arr){
        createHeap(arr);
        //需要循环取出堆顶元素和最后一个元素交换并删除，再从0位置进行调整
        int heapSize= arr.length;
        for(int i=0;i< arr.length;i++){
            //交换0号元素和堆的最后一个元素
            swap(arr,0,heapSize-1);
            //把最后一个元素从堆上删除
            heapSize--;
            //从0号元素开始往下进行调整
            shiftDown(arr,heapSize,0);
        }
    }
    public static void shiftDown(int[] arr,int size,int index){//index是起始位置,size
        //表示当前数组的有效元素大小
        int parent=index;//当前父节点的下标
        int child=parent*2+1;//当前出发节点的左子树的下标
        while(child<size){//当前节点的左子树存在
            //需要找到左右子树中较大的那个
            if(child+1<size && arr[child+1]>arr[child]){//如果右子树存在
                // 并且右子树的值大于左子树
                child=child+1;//让child指向左右子树较大的元素，即右子树。
                // 如果左子树大，child不变还是指向左子树
            }
            //拿父节点和刚才找到的较大的节点的值再做比较,看是否符合大堆的要求
            if(arr[parent]<arr[child]){
                //不满足大堆的要求就交换这两个元素，只是在数组中把这两个元素的位置交换了
                int tmp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=tmp;
            }else{
                break;//调整完毕，已经把父元素放在合适的位置了
            }
            //更新parent和child的位置以备下次调整
            parent=child;
            child=2*parent+1;
        }
    }
    public static void createHeap(int[] arr){
        for(int i=(arr.length-1-1)/2;i>=0;i--){
            shiftDown(arr,arr.length,i);
        }
    }
    public static void swap(int[] arr,int x,int y){
        int tmp=arr[x];
        arr[x]=arr[y];
        arr[y]=tmp;
    }

    //直接选择排序
    public static void selectSort(int[] arr){
        //创建一个变量bound表示已排序区间和待排序区间的边界，
        //[0,bound)已排序[bound,length)是未排序区间
        int bound=0;
        for(;bound< arr.length;bound++){
            //进行打擂台的过程
            for(int cur=bound+1;cur< arr.length;cur++){
                if(arr[cur]<arr[bound]){
                    int tmp=arr[cur];
                    arr[cur]=arr[bound];
                    arr[bound]=tmp;
                }
            }
        }
    }

    //希尔排序
    public static void _ShellSort(int[] arr){
        //指定gap序列，len/2,len/4,len/8……
        int gap= arr.length/2;
        while (gap>=1){
            ShellSort(arr,gap);//具体的插入排序操作
            gap=gap/2;
        }
    }
    public static void ShellSort(int[] arr,int gap){
        //进行分组插入排序,gap表示分的组数，同组的相邻元素，下标差值也是gap
        //下面的代码和插入排序是一样的，尤其是把gap设为1时
        int bound=gap;
        for(;bound< arr.length;bound++){
            int val=arr[bound];
            int cur=bound-gap;
            for(;cur>=0;cur-=gap){
                if(arr[cur]>val){
                    arr[cur+gap]=arr[cur];
                }else{
                    break;
                }
            }
            arr[cur+gap]=val;
        }
    }

    //直接插入排序
    public static void insertSort(int[] arr){
        int bound=1;//[0-bound)是已排序区间，[bound,length)是未排序区间
        for(;bound< arr.length;bound++){//每循环一次进行一次插入
            //要执行具体的插入过程，取出待排序区间的最开始元素
           int a= arr[bound];
            int cur=bound-1;
           for(;cur>=0;cur--){//用a去和前面的所有数据进行比较，
               // a是bound这个位置的数据
               if(arr[cur]>a){
                   //说明a应该插入到arr[cur]之前，就要把arr[cur]这个元素向后搬运
                   arr[cur+1]=arr[cur];
               }else{
                   break;
               }
           }
            arr[cur + 1] = a;
        }
    }

    public static void main(String[] args) {
        int[] arr={9,5,2,7,3,4};
//        insertSort(arr);
//        System.out.println(Arrays.toString(arr));
//        _ShellSort(arr);
//        System.out.println(Arrays.toString(arr));
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
